#include<stdlib.h>
#include<stdio.h>

//插入排序
void insertion_sort(int unsorted_array[], int num_elements){
	int i,j,temp;
	for(i = 2;i<num_elements;i++){
		if(unsorted_array[i]<unsorted_array[i-1]){
			temp = unsorted_array[i];
			unsorted_array[i]=unsorted_array[i-1];
			for(j=i-2;temp < unsorted_array[j];j--){
				unsorted_array[j+1]=unsorted_array[j];
			}
			unsorted_array[j+1]=temp;
		}
	}	
}


//快速排序

int partition(int L[], int low,  int  high, int total_num_elements){//分割
	int temp = L[low];
	int pivot = L[low];
	while(low < high){
		while(low < high&&L[high] >= pivot){
			--high;
		}
		L[low] = L[high];
		while(low < high && L[low] <= pivot){
			++low;
		}
		L[high]=L[low];
	}
	L[low] = temp;
	return low;
}
void QSort(int L[], int low,  int  high, int total_num_elements){
	if(low < high){
		int  pivotpos = partition(L,low,high,total_num_elements);
		
		QSort(L,low,pivotpos-1,total_num_elements);
		QSort(L,pivotpos+1,high,total_num_elements);
		
	}
}

void quick_sort(int unsorted_array[],int num_elements ){
	int low = 0,high = num_elements-1;
	QSort(unsorted_array,low,high,num_elements);
}

//堆排序

//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len){
	int i,temp;
	temp=A[k];
	for(i=2*k;i<=len;i*=2){
		if(i<len&&A[i]<A[i+1]){
			i++;
		}
		if(temp>=A[i]){
			break;
		}else{
			A[k]=A[i];
			k=i;
		}
	}
	A[k]=temp;
}

//建立大根堆
void BuildMaxHeap(int A[],int len){
	int i;
	for(i=len/2;i>=0;i--){
		HeadAdjust(A,i,len);
	}
}

void swap(int *a,int *b){
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
void heap_sort(int unsorted_array[], int num_elements){
	int i;
	BuildMaxHeap(unsorted_array,num_elements);
	for(i=num_elements;i>0;i--){
		swap(&unsorted_array[i],&unsorted_array[0]);
		HeadAdjust(unsorted_array,0,i-1);
	}
}


void main(){
	int num_elements=8;
	int unsorted_array[8]={0,4,3,2,1,7,5,6};//3421
	//QSort(unsorted_array,0,6,num_elements);
	//heap_sort(unsorted_array,num_elements);
	
	insertion_sort(unsorted_array,num_elements);
	//print_array(unsorted_array,num_elements);
	system("pause");
}
